package leetcode.editor.cn;
//给你一个数组 nums ，请你完成两类查询。 
//
// 
// 其中一类查询要求 更新 数组 nums 下标对应的值 
// 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right 
// 
//
// 实现 NumArray 类： 
//
// 
// NumArray(int[] nums) 用整数数组 nums 初始化对象 
// void update(int index, int val) 将 nums[index] 的值 更新 为 val 
// int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元
//素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]） 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：
//["NumArray", "sumRange", "update", "sumRange"]
//[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
//输出：
//[null, 9, null, 8]
//
//解释：
//NumArray numArray = new NumArray([1, 3, 5]);
//numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
//numArray.update(1, 2);   // nums = [1,2,5]
//numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 3 * 10⁴ 
// -100 <= nums[i] <= 100 
// 0 <= index < nums.length 
// -100 <= val <= 100 
// 0 <= left <= right < nums.length 
// 调用 update 和 sumRange 方法次数不大于 3 * 10⁴ 
// 
//
// Related Topics 设计 树状数组 线段树 数组 👍 711 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class NumArray {
    /**
     * 不懂看这个视频
     * https://www.bilibili.com/video/BV1ce411u7qP/?spm_id_from=333.337.search-card.all.click&vd_source=3926f943b1e724ba97d7c2a43d3b3c81
     */
    BITTree bitTree;
    int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        bitTree = new BITTree(n);
        for (int i = 0; i < nums.length; i++) {
            bitTree.update(i + 1, nums[i]);
        }
    }

    public void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        bitTree.update(index + 1, delta);
    }

    public int sumRange(int left, int right) {
        return bitTree.query(right + 1) - bitTree.query(left);
    }
}

class BITTree {
    int[] tree;
    int len;

    // 初始化树状数组
    public BITTree(int n) {
        this.len = n;
        this.tree = new int[n + 1];
    }

    // 可以理解为该值所占原数组区间的长度
    public int lowbit(int i) {
        return i & (-i);
    }

    /**
     *
     * @param i 第几个元素
     * @param delta 更新变化值：加10就是10，减10就是-10
     */
    public void update(int i, int delta) {// update the node and his parent node
        while (i <= len) {
            tree[i] += delta;
            // 上一层需要更新的数
            i += lowbit(i);
        }
    }

    /**
     * 求前i个数的和
     * @param i
     * @return
     */
    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            // 可以理解为从原数组右边往左边求和，只不过tree中的元素代表的意思是一个区间的和
            i -= lowbit(i);
        }
        return sum;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */
//leetcode submit region end(Prohibit modification and deletion)
